package ch.fhnw.ams.sudoku;

/**
 * Implementation of {@link ISolver}.
 * 
 * @author amsler
 *
 */
public class Recursive9by9Solver implements ISolver {
	
	private int[][] inputData;
	private int[][] solution;
	
	
	/*
	 * (non-Javadoc)
	 * @see ch.fhnw.ams.sudoku.ISolver#setData(int[][])
	 */
	@Override
	public void setData(int[][] data) throws InvalidSudokuException {
		if (!isValidSudokuData(data)) {
			throw new InvalidSudokuException();
		}
		this.inputData = data;
		solution = null;
	}
	
	private boolean isValidSudokuData(int[][] data) {
		if (data == null) return false;
		if (data.length != 9) return false;
		
		for (int[] row : data) {
			if (row.length != 9) return false;
			for (int number : row) {
				if (number < 0 || number > 9) return false;
			}
		}
		
		return true;
	}

	/*
	 * (non-Javadoc)
	 * @see ch.fhnw.ams.sudoku.ISolver#generateSolution()
	 */
	@Override
	public void generateSolution() {
		int[][] data = SudokuUtil.copyArray(inputData);
		solve(data, 0, 0);
	}

	/*
	 * (non-Javadoc)
	 * @see ch.fhnw.ams.sudoku.ISolver#hasSolution()
	 */
	@Override
	public boolean hasSolution() {
		if (solution != null) {
			return true;
		}
		
		return false;
	}
	
	/*
	 * (non-Javadoc)
	 * @see ch.fhnw.ams.sudoku.ISolver#getSolution()
	 */
	@Override
	public int[][] getSolution() {
		return solution;
	}
	
	private void solve(int[][] data, int row, int column) {
		if (solution != null) {
			return; //result found
		}
		
		int nextRow = 0;
		int nextColumn = 0;

		// index empty
		if (data[row][column] == 0) { 

			// check all possible numbers for index
			for (int possibleNumber = 1; possibleNumber < 10; possibleNumber++) {
				
				//check sudoku rules
				if (checkRow(data, column, possibleNumber) 
						&& checkColumn(data, row, possibleNumber)
						&& checkBlock(data, row, column, possibleNumber)) {
					
					data[row][column] = possibleNumber;
					
					if (row == 8 && column == 8) {
						solution = data; //result found
						return;
					}

					// next iteration
					if (column == 8) {
						nextRow = row + 1;
						nextColumn = 0;
					} else {
						nextRow = row;
						nextColumn = column + 1;
					}
					solve(data, nextRow, nextColumn);
					if (solution == null) {
						//no result found, reset possible number
						data[row][column] = 0; 
					}
				}
			}
			return; // no possible number found
		}
		
		if (row == 8 && column == 8) {
			solution = data; // result found
			return;
		}

		//next iteration
		if (column == 8) {
			nextRow = row + 1;
			nextColumn = 0;
		} else {
			nextRow = row;
			nextColumn = column + 1;
		}
		solve(data, nextRow, nextColumn); 
	}
	
	private boolean checkColumn(int[][] data, int row, int number) {
		
		for (int column = 0; column < 9 ; column++) {
			if (data[row][column] == number) {
				return false;
			}
		}
		
		return true;
	}
	
	private boolean checkRow(int[][] data, int column, int number) {
		
		for (int row = 0; row < 9 ; row++) {
			if (data[row][column] == number) {
				return false;
			}
		}
		
		return true;
	}
	
	private boolean checkBlock(int[][] data, int row, int column, int number) {
		
		int rowStart = (int) (row / 3) * 3 ;
	    int columnStart = (int) (column / 3) * 3 ;
		
	    for (int rowIdx = rowStart; rowIdx < (rowStart + 3) ; rowIdx++) {
	    	for (int columnIdx = columnStart; columnIdx < (columnStart + 3); columnIdx++) {
	    		if (data[rowIdx][columnIdx] == number) {
	    			return false;
	    		}
	    	}
	    }
	    
		return true;
	}
}
